package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 95. 不同的二叉搜索树 II
 * @author feizns
 * @since 2020/1/7
 */
public class GenerateTrees {

    public static void main(String[] args) {
        List<TreeNode> nodes = generateTrees(4);
        System.out.println(nodes.size());
    }

    private static Integer val(TreeNode ret) {
        return ret == null ? null : ret.val;
    }

    public static List<TreeNode> generateTrees(int n) {
        return generateTrees(1, n);
    }

    public static List<TreeNode> generateTrees(int l, int r) {
        List<TreeNode> ret = new LinkedList<>();
        if ( l == r )
            ret.add(new TreeNode(l));
        else if ( l < r ) {
            for (int i = l; i <= r; i++) {
                List<TreeNode> left = generateTrees(l, i - 1);
                List<TreeNode> right = generateTrees(i + 1, r);
                if ( !left.isEmpty() && !right.isEmpty() ) {
                    for (TreeNode ln : left) {
                        for (TreeNode rn : right) {
                            TreeNode tmp = new TreeNode(i);
                            tmp.left = ln;
                            tmp.right = rn;
                            ret.add(tmp);
                        }
                    }
                } else if ( !left.isEmpty() ){
                    for (TreeNode node : left) {
                        TreeNode tmp = new TreeNode(i);
                        tmp.left = node;
                        ret.add(tmp);
                    }
                } else if ( !right.isEmpty() ){
                    for (TreeNode node : right) {
                        TreeNode tmp = new TreeNode(i);
                        tmp.right = node;
                        ret.add(tmp);
                    }
                }
            }
        }
        return ret;
    }

}
